/* 动态规划之 最长上升子序列 */


#include <algorithm>
#include<vector>
#include<functional>
#include<iostream>
using namespace std;


int main()
{
	constexpr int N = 7;
	int a[N] = { 1, 7, 3, 5, 9, 6, 8 };

	vector<int> vecMRS[N];
	int mrsLen[N]{ 1, 0 };
	vecMRS[0].push_back(a[0]);

	for (int i = 1; i < N; i++)
	{
		int tmpMaxMRSLen = 0;
		int lastMRSIdx = -1;
		for (int j = 0; j < i; j++)
		{
			if (a[i] > a[j])
			{
				if (tmpMaxMRSLen < mrsLen[j])
				{
					tmpMaxMRSLen = mrsLen[j];
					lastMRSIdx = j;
				}
				
			}
		}

		mrsLen[i] = tmpMaxMRSLen + 1;
		if (lastMRSIdx != -1)
		{
			vecMRS[i].assign(vecMRS[lastMRSIdx].begin(), vecMRS[lastMRSIdx].end());
		}
		vecMRS[i].push_back(a[i]);
	}

	int maxMrsLen = 1;
	int maxMrsIdx = 0;
	for (int i = 1; i < N; i++)
	{
		if (maxMrsLen < mrsLen[i])
		{
			maxMrsLen = mrsLen[i];
			maxMrsIdx = i;
		}
	}

	cout << "Maxmium rising sequence len is: " << maxMrsLen << ", and the sequence is: \n";
	for_each(vecMRS[maxMrsIdx].begin(), vecMRS[maxMrsIdx].end(), [](int e) {cout << e << " "; });
	cout<< "\n";
}
